A relational database consists of a set of relations, each of which is a set of equal-length tuples of values. A relation can be viewed as a rectangular array of values, where each row is a tuple and each column, called an "attribute", has a name. A "primary key" for a relation is some subset of its attributes with the property that the values of all attributes of a tuple are uniquely determined by values for the primary key attributes. Queries on relational databases are answered by the relational operations "select", "project" and "join" to relations in the database.
For a thorough treatment of relational databases, refer to one of the many texts on the subject, for example:
J.D. Ullman "Principles of Database Systems" Computer Science Press (1982)
Overview
---------
The classes and universal methods in the file "RDB Tools" provide tools for building and maintaining a one-file, single-user relational database. These tools are not designed for multi-user databases since they lack such facilities as locking during updates: they could, however, be extended fairly easily. No facilities are provided for enforcing types of relation attributes.
A database and the relations in it are represented by instances of various classes, each of which controls access to the database file, so the user does not need to directly access the file or tables in it. These instances are stored in the database file together with the data. Three kinds of relations are maintained, as follows.
• Basic relations provide the underlying data in the database, directly stored in the database file.
• Implicit relations provide read-only access to the basic relations, either by simply reading them, or by constructing on demand the tuples of relations corresponding to the application of some relational operations.
• Derived relations, like basic ones, store their tuples in the database file; like implicit relations, however, they are computed by relational operations. This means that when basic relations are updated, the data stored for derived relations also must be modified. This is done by transaction-based propagation of modifications, under the user's control.
The tuples of relations are represented as lists. Basic and derived relations (ie those that keep their data in the file) must have a primary key, which is used for uniqueness checking as tuples are written into the database file. The transaction-based updating of derived relations depends on this property.
In the file "RDB Tools", methods with names beginning with an uppercase letter are "top-level" methods to be called directly. All other methods are "service" methods called by "top-level" ones. In most cases, the comments on methods, attributes and classes describe them adequately, so we will concentrate in these notes on drawing the user's attention to important points. In particular, we will state certain conditions which ensure that the provided classes and methods behave correctly; these are marked with [*]. Since our aim is to provide tools for building applications, we leave it to the user to meet these conditions; the alternative would be to fill the code with protective mechanisms which would be unnecessary in a correctly constructed application. The first such condition follows.
[*] Do not directly generate instances of the supplied classes or directly set the attributes of instances of these classes. These actions will be performed by the supplied methods.
In the following, if X is a class we use the notation «X» as shorthand for "instance of class X or subclass of X".
================
The class "Database"
================
Each «Database» maintains a file (type REDB) of tables, representing relations, each of which may be basic or derived, as described above. The «Database» itself is also stored in the file, and rewritten there whenever its structure changes. When a database file is open, the corresponding «Database» is kept in the class attribute "currentDB" of "Database".
"Database" has a class attribute "pending" which contains a list of all «Basic»s which
(a) have had tuples added or deleted, and
(b) have dependent «Derived»s which must be updated to reflect these changes.
(see Database/Update, Basic/Add tuple, Basic/Delete tuple and Basic/Set pending).
The universal method "Make DB" creates a «Database» and the corresponding file, which it opens. It fails if a file of the given name exists at the location specified by the supplied volume identifier.
Saves the current «Database» into the file, closes the file and discards «Database».
[*] It is important to execute this before saving your Prograph database application. If you do not, then subsequent attempts to use the application may cause a crash since the «Database» in the "currentDB" attribute of class "Database" will have invalid path identifiers.
This creates a new «Basic» in the list of relations of a database, and makes three tables in the database file, one for the current tuples of a relation, and the other two for updating purposes.
[*] The new relation name must be different from that of any relation in the database.
[*] The key must be a non-empty subset (list) of the list of attributes names.
[*] The elements of the list of attribute names must be distinct.
[*] Should be applied to any «Database» after modifying any relations, otherwise queries will give wrong answers, based on the old state of the relations (see methods Basic/Add tuple and Basic/Delete tuple).
The database can be closed without first applying "Update" since the update transactions are in the file, so updating can be done when the file is reopened.
"Direct" is an abstract class (ie is never intended to be used to construct instances). A «Direct» represents a relation that is directly stored in the database, and corresponds to three database file tables, a main table, a DELETE table and an ADD table. A «Basic» corresponds to an underlying relation, while a «Derived» corresponds to a relation obtained from others by some relational algebra computation. The attribute "query" of a «Derived» contains an «Implicit» specifying this calculation. The query is used for filling the database file table corresponding to the «Derived», and for updating it when another relation on which it depends is changed.
Each «Direct» can have dependents, which are «Derived»s that the «Direct» in the computation of their tuples.
-----------------------------------------------
Methods of classes "Direct", "Basic" and "Derived"
-----------------------------------------------
Direct/Delete
Derived/Delete
[*] These should be applied only to a relation which has no read-only copies, so first check that attribute "copies" contains the empty list.
If the «Basic» has no dependents, these methods directly modify the corresponding main table. Otherwise, they modify the ADD and DELETE tables. The effects of these changes will not be seen until after the method "Database/Update" has been applied to a «Database», updating all modified «Basic»s and their dependent «Derived»s. Note that these changes may propagate extensively if there are many derived relations. This mechanism is used because maintaining the consistency of directly stored derived relations is expensive (particularly joins), so after a period of adding and deleting, all affected relations can be updated "en masse".
[*] After a sequence of changes have been made to a «Basic», "Post changes" must be applied to it to ensure that subsequent updating propagates these changes through dependent «Derived»s.
Makes a «Read-direct», providing read-only access to a «Direct».
==================================
The class subtree rooted in class "Implicit"
==================================
"Implicit" is an abstract class. An «Implicit» realises a read-only virtual relation by providing methods for computing tuples for the virtual relation. An «Implicit» is either a «Read-direct» which provides read access to a «Direct», or a «Query» which defines a virtual relation resulting from a relational operation on other «Implicit»s. "Query" is an abstract class. A «Query» is either a «Selection», a «Projection» or a «Join».
The primary key and attribute names of a query is computed from the primary keys and attribute names of the relations from which it is composed. These computations are performed by overshadowing get methods "attributes" and "key" in various classes. Each computed attribute name has an appended suffix consisting of the name of the underlying relation from which it originates, together with an integer index.
Each «Implicit» maintains a cursor into the relation it represents.
Constructs a «Selection» implementing the relational selection operation. The second input is the name of the method to be used for selecting tuples. For example, if your application is to compile some selection mechanism from some query language, you could remove the second input from "Implicit/Select" and set the default value of the attribute "method" of class "Selection" to the name of a fixed selection method. This fixed method could then refer to some persistent (or perhaps an added attribute) for your compiled selection mechanism.
Constructs a «Projection» implementing the relational project operation. The second input is a list of names of attributes on which to project. It can contain repetitions.
Constructs a «Join» implementing the relational join operation. The third input is a list of pairs of names of attributes on which the join is performed.
(Methods in the classes "Read-direct", "Selection", "Projection" and "Join"). Each reads a particular tuple from the relation. All except "Current" reposition the cursor into the relation, and all will fail if the requested tuple does not exist.
(Methods in the classes "Read-direct", "Query" and "Join"). "Delete" removes all underlying «Read-direct»s from the copy lists of the corresponding «Direct»s.
[*] You must execute "Delete" on any «Implicit» that you no longer intend to use.
Creates a «Derived» based on the supplied query, and the corresponding database file tables.
==========================
Examples to Illustrate RDB Tools
==========================
The file "RDB Examples" contains some universal methods that give some simple illustrations of the use of "RDB Tools". To use it , load it and (incrementally) load "RDB Tools" together. Since the purpose of "RDB Tools" and "RDB Examples" is to provide a relational database engine and a simple illustration of it, no attempt has been made in the example file to make sophisticated interfaces.
These universal methods bear brief comments, and are otherwise fairly self explanatory. The methods "TEST QUERY", "year1 science", "MATH!!)" and "ADD DERIVED" apply to the "university" database file, so before running these methods, open this file using the method OPEN.
